class Solution
{
public:
    int maxResult(vector<int> &nums, int k)
    {
        int n = nums.size();
        deque<int> localMaxIndex;
        vector<int> maxScoreDp(n, 0);
        maxScoreDp[0] = nums[0];
        for (int i = 1; i < n; ++i)
        {
            while (!localMaxIndex.empty())
            {
                if (localMaxIndex.front() < i - k)
                {
                    localMaxIndex.pop_front();
                }
                else if (maxScoreDp[localMaxIndex.back()] < maxScoreDp[i - 1])
                {
                    localMaxIndex.pop_back();
                }
                else
                {
                    break;
                }
            }
            localMaxIndex.push_back(i - 1);
            maxScoreDp[i] = nums[i] + maxScoreDp[localMaxIndex.front()];
        }
        return maxScoreDp[n - 1];
    }
};